<?php
/*
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

 

提示：

    0 <= nums.length <= 105
    -109 <= nums[i] <= 109
    nums 是一个非递减数组
    -109 <= target <= 109

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
 */

class Solution
{

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    public function searchRange($nums, $target)
    {
        return [$this->search($nums, $target, "first"), $this->search($nums, $target, "last")];
    }

    public function search($nums, $target, $search)
    {
        $left  = 0;
        $right = count($nums) - 1;
        while ($left <= $right) {
            $mid = floor(($right - $left) / 2) + $left;
            if ($nums[$mid] == $target) {
                if ($search == "first") {
                    if ($mid == 0 || $nums[$mid - 1] != $target) {
                        return $mid;
                    }
                    $right = $mid - 1;
                } else {
                    if ($mid == count($nums) - 1 || $nums[$mid + 1] != $target) {
                        return $mid;
                    }
                    $left = $mid + 1;
                }
            } elseif ($nums[$mid] > $target) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }
        return -1;
    }

}
